Arbitrary conditioning is an important problem in unsupervised learning, where we seek to model the conditional densities $p(\mathbf{x}_u \mid \mathbf{x}_o)$ that underly some data, for all possible non-intersecting subsets $o, u \subset \{1, \dots, d\}$. However, the vast majority of density estimation only focuses on modeling the joint distribution $p(\mathbf{x})$, in which important conditional dependencies between features are opaque. We propose a simple and general framework, coined Posterior Matching, that enables Variational Autoencoders (VAEs) to perform arbitrary conditioning, without modification to the VAE itself. Posterior Matching applies to the numerous existing VAE-based approaches to joint density estimation, thereby circumventing the specialized models required by previous approaches to arbitrary conditioning. We find that Posterior Matching is comparable or superior to current state-of-the-art methods for a variety of tasks with an assortment of VAEs (e.g.~discrete, hierarchical, VaDE).

Arbitrary conditioning is an important problem in unsupervised learning, where we seek to model the conditional densities p(\mathbf{x}_u \mid \mathbf{x}_o) that underly some data, for all possible non-intersecting subsets o, u \subset \{1, \dots, d\} . However, the vast majority of density estimation only focuses on modeling the joint distribution p(\mathbf{x}), in which important conditional dependencies between features are opaque. We propose a simple and general framework, coined Posterior Matching, that enables Variational Autoencoders (VAEs) to perform arbitrary conditioning, without modification to the VAE itself. Posterior Matching applies to the numerous existing VAE-based approaches to joint density estimation, thereby circumventing the specialized models required by previous approaches to arbitrary conditioning. We find that Posterior Matching is comparable or superior to current state-of-the-art methods for a variety of tasks with an assortment of VAEs (e.g.

Arbitrary conditioning is an important problem in unsupervised learning, where we seek to model the conditional densities $p(\mathbf{x}_u \mid \mathbf{x}_o)$ that underly some data, for all possible non-intersecting subsets $o, u \subset \{1, \dots , d\}$. However, the vast majority of density estimation only focuses on modeling the joint distribution $p(\mathbf{x})$, in which important conditional dependencies between features are opaque. We propose a simple and general framework, coined Posterior Matching, that enables any Variational Autoencoder (VAE) to perform arbitrary conditioning, without modification to the VAE itself. Posterior Matching applies to the numerous existing VAE-based approaches to joint density estimation, thereby circumventing the specialized models required by previous approaches to arbitrary conditioning. We find that Posterior Matching achieves performance that is comparable or superior to current state-of-the-art methods for a variety of tasks.

This paper considers a target localization problem where at any given time an agent can choose a region to query for the presence of the target in that region. The measurement noise is assumed to be increasing with the size of the query region the agent chooses. Motivated by practical applications such as initial beam alignment in array processing, heavy hitter detection in networking, and visual search in robotics, we consider practically important complexity constraints/metrics: \textit{time complexity}, \textit{computational and memory complexity}, and the complexity of possible query sets in terms of geometry and cardinality. Two novel search strategy, $dyaPM$ and $hiePM$, are proposed. Pertinent to the practicality of out solutions, $dyaPM$ and $hiePM$ are of a connected query geometry (i.e. query set is always a connected set) implemented with low computational and memory complexity. Additionally, $hiePM$ has a hierarchical structure and, hence, a further reduction in the cardinality of possible query sets, making $hiePM$ practically suitable for applications such as beamforming in array processing where memory limitations favors a smaller codebook size. Through a unified analysis with Extrinsic Jensen Shannon (EJS) Divergence, $dyaPM$ is shown to be asymptotically optimal in search time complexity (asymptotic in both resolution (rate) and error (reliability)). On the other hand, $hiePM$ is shown to be near-optimal in rate. In addition, both $hiePM$ and $dyaPM$ are shown to outperform prior work in the non-asymptotic regime.